package com.company.OfferGuide;

import java.util.PriorityQueue;

public class 数据流中的中位数 {

    public static void main(String[] args) {
        数据流中的中位数 object = new 数据流中的中位数();
        object.MedianFinder();
        object.addNum(1);
        object.addNum(2);
        System.out.println(object.findMedian());
        object.addNum(3);
        System.out.println(object.findMedian());
    }

    private PriorityQueue<Integer> high;
    private PriorityQueue<Integer> low;
    int size = 0;
    /** initialize your data structure here. */
    public void MedianFinder() {
        low = new PriorityQueue<>();
        high = new PriorityQueue<>((o1,o2) -> o2 - o1);
    }

    public void addNum(int num) {
        size++;
        if (size % 2 == 1) {
            if (!low.isEmpty() && num > low.peek()) {
                low.offer(num);
                num = low.poll();
            }
            high.offer(num);
        } else {
            if (!high.isEmpty() && num < high.peek()) {
                high.offer(num);
                num = high.poll();
            }
            high.offer(num);
        }
    }

    public double findMedian() {
        if (size % 2 == 1) {
            return high.peek();
        } else {
            return (high.peek() + low.peek())/2.0;
        }
    }

}
